﻿#include <iostream>

#define MAX(a, b) (a > b ? a : b)

static int getMax(const int* numbers, const size_t numberSize)
{
	int max = -1;
	for (int i = 0; i < numberSize; i++)
	{
		if (max < numbers[i])
		{
			max = numbers[i];
		}
	}

	return max;
}

/**
 * 常规方法，硬判断
 */
static int normalMethod(const int* numbers, const size_t numberSize)
{
	int max = 0;
	for (int i = 1; i < numberSize; i++)
	{
		int leftMax = getMax(numbers, i);
		int rightMax = getMax(numbers + i, numberSize - i);
		int absNum = abs(leftMax - rightMax);
		if (max < absNum)
		{
			max = absNum;
		}
	}

	return max;
}

/**
 * 整个数组的最大值一定在左半部分，或者右半部分.
 * 当最大值不在一部分时，就向中间推进这一部分
 */
static int anotherMethod(const int* numbers, const size_t numberSize)
{
	int maxIndex = 0;
	int max = 0;
	for (int i = 0; i < numberSize; i++)
	{
		if (max < numbers[i])
		{
			max = numbers[i];
			maxIndex = i;
		}
	}

	int lEdge = 1; // 左半部分<lEdge
	int rEdge = numberSize - 1; // 右半部分>=rEdge
	int* maxArr = (int*)malloc(sizeof(int) * numberSize);
	memset(maxArr, 0, sizeof(int) * numberSize);
	int lMax = 0;
	int rMax = 0;

	while (lEdge <= rEdge)
	{
		if (lEdge <= maxIndex)
		{
			// 右半部分的最大值即为整个数组的最大值

			if (lMax < numbers[lEdge - 1])
			{
				lMax = numbers[lEdge - 1];
			}

			maxArr[lEdge - 1] = abs(lMax - max);
			++lEdge;
		}
		else
		{
			// 左半部分的最大值即为整个数组的最大值

			if (rMax < numbers[rEdge])
			{
				rMax = numbers[rEdge];
			}

			maxArr[rEdge] = abs(rMax - max);
			--rEdge;
		}
	}

	max = 0;
	for (int i = 0; i < numberSize; i++)
	{
		if (max < maxArr[i])
		{
			max = maxArr[i];
		}
	}

	return max;
}

/**
 * 方法2
 * 设arr的最大值是arrMax，
 * 情况1：将数组分为两部分，0-N-2作为左半部分，N-1作为右半部分，假设arr的最大值在0-N-2中，
 * 那么这种情况下，右半部分在向左扩的过程中，最大值不可能再比arr[N-1]小了，设a=arrMax-arr[N-1]
 * 情况2: 将数组分为两部分, 0作为左半部分，1-N-1作为右半部分，假设arr的最大值在1-N-1中，那么这种情况下，
 * 左半部分向右扩的过程中，最大值不可能再比arr[0]小了，设b=arrMax-arr[0]
 * 则最后的答案就是a和b较大的那个。
 * @param arr
 * @return
 */
static int anotherMethod2(const int* arr, const size_t len) {
	if (!arr) return 0;

	int size = len;
	if (size <= 1) return 0;

	if (size == 2) return abs(arr[0] - arr[1]);

	int max = 0;
	for (int i = 0; i < size; i++) {
		if (max < arr[i]) {
			max = arr[i];
		}
	}

	int a = max - arr[size - 1];
	int b = max - arr[0];
	return MAX(a, b);
}

/**
 * 给定一个数组arr长度为N，你可以把任意长度大于0且小于N的前缀作为左部分，
 * 剩下的作为右部分。但是每种划分下都有左部分的最大值和右部分的最大值，请返回
 * 左部分最大值减去右部分最大值的绝对值的最大值。
 */
int main_MaxAbsForLeftMaxMinusRightMax()
{
	int numbers[] = { 3,5,3,4,8,10,2,6,7,1 };
	int count = sizeof(numbers) / sizeof(int);
	int max = normalMethod(numbers, count);
	int max2 = anotherMethod(numbers, count);
	int max3 = anotherMethod2(numbers, count);
	printf("%d %d %d", max, max2, max3);
	return 0;
}